{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Cost to Hire K Workers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mincostToHireWorkers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #雇佣 K 名工人的最低成本"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code>&nbsp;名工人。&nbsp;给定两个数组&nbsp;<code>quality</code>&nbsp;和&nbsp;<code>wage</code>&nbsp;，其中，<code>quality[i]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;名工人的工作质量，其最低期望工资为&nbsp;<code>wage[i]</code>&nbsp;。</p>\n",
    "\n",
    "<p>现在我们想雇佣&nbsp;<code>k</code>&nbsp;名工人组成一个<em>工资组。</em>在雇佣&nbsp;一组 <code>k</code>&nbsp;名工人时，我们必须按照下述规则向他们支付工资：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。</li>\n",
    "\t<li>工资组中的每名工人至少应当得到他们的最低期望工资。</li>\n",
    "</ol>\n",
    "\n",
    "<p>给定整数 <code>k</code> ，返回 <em>组成满足上述条件的付费群体所需的最小金额&nbsp;</em>。在实际答案的&nbsp;<code>10<sup>-5</sup></code>&nbsp;以内的答案将被接受。。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入： </strong>quality = [10,20,5], wage = [70,50,30], k = 2\n",
    "<strong>输出： </strong>105.00000\n",
    "<strong>解释：</strong> 我们向 0 号工人支付 70，向 2 号工人支付 35。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入： </strong>quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3\n",
    "<strong>输出： </strong>30.66667\n",
    "<strong>解释： </strong>我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == quality.length == wage.length</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= quality[i], wage[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-cost-to-hire-k-workers](https://leetcode.cn/problems/minimum-cost-to-hire-k-workers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-cost-to-hire-k-workers](https://leetcode.cn/problems/minimum-cost-to-hire-k-workers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,20,5]\\n[70,50,30]\\n2', '[3,1,10,10,1]\\n[4,8,2,2,7]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        n = len(quality)\n",
    "        ind = list(range(n))\n",
    "        ind.sort(key=lambda it: wage[it]/quality[it])\n",
    "        ans = inf\n",
    "        pre = 0\n",
    "        stack = []\n",
    "        for i in ind:\n",
    "            if len(stack) == k-1:\n",
    "                cur = (pre+quality[i])*wage[i]/quality[i]\n",
    "                if cur < ans:\n",
    "                    ans = cur\n",
    "            heapq.heappush(stack, -quality[i])\n",
    "            pre += quality[i]\n",
    "            if len(stack) == k:\n",
    "                pre += heapq.heappop(stack)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        pairs=sorted(zip(quality,wage),key=lambda p:p[1]/p[0])\n",
    "        totalq=0\n",
    "        heap=[]\n",
    "        for q,w in pairs[:k-1]:\n",
    "            heappush(heap,-q)\n",
    "            totalq+=q\n",
    "        ans=inf\n",
    "        totalc=0\n",
    "        for q,w in pairs[k-1:]:\n",
    "            totalq+=q\n",
    "            totalc=totalq*w/q\n",
    "            ans=min(totalc,ans)\n",
    "            totalq+=heappushpop(heap,-q)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        pairs = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])\n",
    "        ans = inf\n",
    "        totalq = 0\n",
    "        h = []\n",
    "        for q, w in pairs[:k - 1]:\n",
    "            totalq += q\n",
    "            heappush(h, -q)\n",
    "        for q, w in pairs[k - 1:]:\n",
    "            totalq += q\n",
    "            heappush(h, -q)\n",
    "            ans = min(ans, w / q * totalq)\n",
    "            totalq += heappop(h)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        pairs=sorted(zip(wage,quality),key=lambda x:x[0]/x[1])\n",
    "        h=[]\n",
    "        totalq=0\n",
    "        for w,q in pairs[:k-1]:\n",
    "            totalq+=q\n",
    "            heappush(h,-q)\n",
    "        res=inf\n",
    "        for w,q in pairs[k-1:]:\n",
    "            totalq+=q\n",
    "            heappush(h,-q)\n",
    "            res=min(res,totalq*w/q)\n",
    "            totalq+=heappop(h)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        n = len(quality)\n",
    "        ind = list(range(n))\n",
    "        ind.sort(key=lambda it: wage[it]/quality[it])\n",
    "        ans = inf\n",
    "        pre = 0\n",
    "        stack = []\n",
    "        for i in ind:\n",
    "            heapq.heappush(stack, -quality[i])\n",
    "            pre += quality[i]\n",
    "            if len(stack) > k:\n",
    "                pre += heapq.heappop(stack)\n",
    "            if len(stack) == k:\n",
    "                cur = pre*wage[i]/quality[i]\n",
    "                if cur < ans:\n",
    "                    ans = cur\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        pairs = sorted(zip(quality, wage), key=lambda p: p[1]/p[0])\n",
    "        res = inf\n",
    "        total_q = 0\n",
    "        pq = []\n",
    "\n",
    "        for q, w in pairs[:k-1]:\n",
    "            total_q += q\n",
    "            heappush(pq, -q)\n",
    "\n",
    "        for q, w in pairs[k-1:]:\n",
    "            total_q += q\n",
    "            heappush(pq, -q)\n",
    "            res = min(res, w/q * total_q)\n",
    "            total_q += heappop(pq)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        pairs=sorted(zip(wage,quality),key=lambda x:x[0]/x[1])\n",
    "        h=[]\n",
    "        totalq=0\n",
    "        for w,q in pairs[:k-1]:\n",
    "            totalq+=q\n",
    "            heappush(h,-q)\n",
    "        res=inf\n",
    "        for w,q in pairs[k-1:]:\n",
    "            totalq+=q\n",
    "            heappush(h,-q)\n",
    "            res=min(res,totalq*w/q)\n",
    "            totalq+=heappop(h)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        qw = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])  # 按照 r 值排序\n",
    "        h = [-q for q, _ in qw[:k]]  # 加负号变成最大堆\n",
    "        heapify(h)\n",
    "        sum_q = -sum(h)\n",
    "        ans = sum_q * qw[k - 1][1] / qw[k - 1][0]  # 选 r 值最小的 k 名工人组成当前的最优解\n",
    "        for q, w in qw[k:]:\n",
    "            if q < -h[0]:  # sum_q 可以变小，从而可能得到更优的答案\n",
    "                sum_q += heapreplace(h, -q) + q  # 更新堆顶和 sum_q\n",
    "                ans = min(ans, sum_q * w / q)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        wqs=[(float(w)/q,q,w) for w,q in zip(wage,quality)]\n",
    "        wqs.sort()\n",
    "        res=99999999999999999999999\n",
    "        min_q=0\n",
    "        pq=[]\n",
    "        for i,(f,q,w) in enumerate(wqs):\n",
    "            min_q+=q\n",
    "            heapq.heappush(pq,-q)\n",
    "            if i>=k:\n",
    "                min_q-=-heapq.heappop(pq)\n",
    "            if i>=k-1:\n",
    "                res=min(res,min_q*f)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\r\n",
    "        qw = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])  # 按照 r 值排序\r\n",
    "        h = [-q for q, _ in qw[:k]]  # 加负号变成最大堆\r\n",
    "        heapify(h)\r\n",
    "        sum_q = -sum(h)\r\n",
    "        ans = sum_q * qw[k - 1][1] / qw[k - 1][0]  # 选 r 值最小的 k 名工人组成当前的最优解\r\n",
    "        for q, w in qw[k:]:\r\n",
    "            if q < -h[0]:  # sum_q 可以变小，从而可能得到更优的答案\r\n",
    "                sum_q += heapreplace(h, -q) + q  # 更新堆顶和 sum_q\r\n",
    "                ans = min(ans, sum_q * w / q)\r\n",
    "        return ans\r\n",
    "        \r\n",
    "    # 贪心 + 优先队列（最小堆）\r\n",
    "    def mincostToHireWorkers2(self, quality: List[int], wage: List[int], k: int) -> float:\r\n",
    "        pairs = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])\r\n",
    "        ans = inf\r\n",
    "        totalq = 0\r\n",
    "        h = []\r\n",
    "        for q, w in pairs[:k - 1]:\r\n",
    "            totalq += q\r\n",
    "            heappush(h, -q)\r\n",
    "        for q, w in pairs[k - 1:]:\r\n",
    "            totalq += q\r\n",
    "            heappush(h, -q)\r\n",
    "            ans = min(ans, w / q * totalq)\r\n",
    "            totalq += heappop(h)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        qw = sorted(zip(quality,wage),key=lambda x:x[1]/x[0])\n",
    "        h = [-q for q,_ in qw[:k]]\n",
    "        heapify(h)\n",
    "        sum_q = -sum(h)\n",
    "        ans = sum_q * qw[k-1][1] / qw[k-1][0]\n",
    "        for q,w in qw[k:]:\n",
    "            if q<-h[0]:\n",
    "                sum_q += heapreplace(h,-q)+q\n",
    "                ans = min(ans,sum_q*w/q)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        pairs = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])\n",
    "        ans = inf\n",
    "        totalq = 0\n",
    "        h = []\n",
    "        for q, w in pairs[:k - 1]:\n",
    "            totalq += q\n",
    "            heappush(h, -q)\n",
    "        for q, w in pairs[k - 1:]:\n",
    "            totalq += q\n",
    "            heappush(h, -q)\n",
    "            ans = min(ans, w / q * totalq)\n",
    "            totalq += heappop(h)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        pairs=sorted(zip(wage,quality),key=lambda x:x[0]/x[1])\n",
    "        h=[]\n",
    "        totalq=0\n",
    "        for w,q in pairs[:k-1]:\n",
    "            totalq+=q\n",
    "            heappush(h,-q)\n",
    "        res=inf\n",
    "        for w,q in pairs[k-1:]:\n",
    "            totalq+=q\n",
    "            heappush(h,-q)\n",
    "            res=min(res,totalq*w/q)\n",
    "            totalq+=heappop(h)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        qw = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])\n",
    "        h = [-q for q, _ in qw[:k]]\n",
    "        heapify(h)\n",
    "        sum_q = -sum(h)\n",
    "        ans = sum_q * qw[k - 1][1] / qw[k - 1][0]\n",
    "        for q, w in qw[k:]:\n",
    "            if q < -h[0]:\n",
    "                sum_q += heapreplace(h, -q) + q\n",
    "                ans = min(ans, sum_q * w / q)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        pairs = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])\n",
    "        ans = inf\n",
    "        totalq = 0\n",
    "        h = []\n",
    "        for q, w in pairs[:k - 1]:\n",
    "            totalq += q\n",
    "            heappush(h, -q)\n",
    "        for q, w in pairs[k - 1:]:\n",
    "            totalq += q \n",
    "            heappush(h, -q)\n",
    "            ans = min(ans, w / q * totalq)\n",
    "            totalq += heappop(h)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        a=[[w/q,q] for w,q in zip(wage,quality)]\n",
    "        a.sort()\n",
    "        res, qsum = inf, 0\n",
    "        h = []\n",
    "        for r, q in a:\n",
    "            qsum += q\n",
    "            if len(h) == k - 1:\n",
    "                res = min(res, qsum * r)\n",
    "            heapq.heappush(h, -q)\n",
    "            if len(h) >= k:\n",
    "                qsum += heapq.heappop(h)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "class Solution:\r\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\r\n",
    "        q_w=sorted(zip(quality,wage),key=lambda x:x[1]/x[0])\r\n",
    "        total_q=0\r\n",
    "        ans=float('inf')\r\n",
    "        h=[]\r\n",
    "        for i in range(k-1):\r\n",
    "            total_q+=q_w[i][0]\r\n",
    "            heapq.heappush(h,-q_w[i][0])\r\n",
    "        for i in  range(k-1,len(quality)):\r\n",
    "            q,w=q_w[i]\r\n",
    "            total_q+=q\r\n",
    "            ans=min(ans,total_q*w/q)\r\n",
    "            total_q+=heapq.heappushpop(h,-q)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        qw = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])  # 按照 r 值排序\n",
    "        h = [-q for q, _ in qw[:k]]  # 加负号变成最大堆\n",
    "        heapify(h)\n",
    "        sum_q = -sum(h)\n",
    "        ans = sum_q * qw[k - 1][1] / qw[k - 1][0]  # 选 r 值最小的 k 名工人组成当前的最优解\n",
    "        for q, w in qw[k:]:\n",
    "            if q < -h[0]:  # sum_q 可以变小，从而可能得到更优的答案\n",
    "                sum_q += heapreplace(h, -q) + q  # 更新堆顶和 sum_q\n",
    "                ans = min(ans, sum_q * w / q)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        a = sorted(zip(quality, wage), key=lambda x: x[1] / x[0])\n",
    "        h = []\n",
    "        s = 0\n",
    "        for i in range(k):\n",
    "            s += a[i][0]\n",
    "            heapq.heappush(h, -a[i][0])\n",
    "        d = a[k - 1][1] / a[k - 1][0]\n",
    "        ans = s * d\n",
    "        for i in range(k, len(a)):\n",
    "            if a[i][0] < -h[0]:\n",
    "                s += a[i][0] + h[0]\n",
    "                heapq.heapreplace(h, -a[i][0])\n",
    "                d = a[i][1] / a[i][0]\n",
    "                ans = min(ans, s * d)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        qw = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])  # 按照 r 值排序\n",
    "        h = [-q for q, _ in qw[:k]]  # 加负号变成最大堆\n",
    "        heapify(h)\n",
    "        sum_q = -sum(h)\n",
    "        ans = sum_q * qw[k - 1][1] / qw[k - 1][0]  # 选 r 值最小的 k 名工人组成当前的最优解\n",
    "        for q, w in qw[k:]:\n",
    "            if q < -h[0]:  # sum_q 可以变小，从而可能得到更优的答案\n",
    "                sum_q += heapreplace(h, -q) + q  # 更新堆顶和 sum_q\n",
    "                ans = min(ans, sum_q * w / q)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        wage_per_quality = [(w/q, q) for q,w in zip(quality, wage)]\n",
    "        wage_per_quality.sort(key = lambda a:a[0])\n",
    "        queue = []\n",
    "        sumq = 0\n",
    "        rs = float('inf')\n",
    "        for wq, q in wage_per_quality:\n",
    "            if len(queue) < k:\n",
    "                heapq.heappush(queue,-q)\n",
    "                sumq += q\n",
    "            elif q<-queue[0]:\n",
    "                tmp = -heapq.heappop(queue)\n",
    "                heapq.heappush(queue,-q)\n",
    "                sumq += q-tmp\n",
    "            # print(wq,sumq,q)\n",
    "            if len(queue) == k:\n",
    "                \n",
    "                rs = min(rs,wq*sumq)\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        pairs = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])\n",
    "        ans = inf\n",
    "        totalq = 0\n",
    "        h = []\n",
    "        for q, w in pairs[:k - 1]:\n",
    "            totalq += q\n",
    "            heappush(h, -q)\n",
    "        for q, w in pairs[k - 1:]:\n",
    "            totalq += q\n",
    "            heappush(h, -q)\n",
    "            ans = min(ans, w / q * totalq)\n",
    "            totalq += heappop(h)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        pairs = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])\n",
    "        ans = inf\n",
    "        totalq = 0\n",
    "        h = []\n",
    "        for q, w in pairs[:k - 1]:\n",
    "            totalq += q\n",
    "            heappush(h, -q)\n",
    "        for q, w in pairs[k - 1:]:\n",
    "            totalq += q\n",
    "            heappush(h, -q)\n",
    "            ans = min(ans, w / q * totalq)\n",
    "            totalq += heappop(h)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        ls=sorted(zip(quality,wage),key=lambda x:x[1]/x[0])\n",
    "        order=[]\n",
    "        for i in range(k):\n",
    "            order.append(ls[i][0])\n",
    "        #print(order)\n",
    "        order.sort()\n",
    "        lastsum=sum(order)\n",
    "        #print(lastsum)\n",
    "        ans=lastsum*ls[k-1][1]/ls[k-1][0]\n",
    "        #print(ans)\n",
    "        last=order[-1]\n",
    "        n=len(quality)\n",
    "        #print(ls)\n",
    "        for i in range(k,n):\n",
    "            #print(ls[i][0],last)\n",
    "            if ls[i][0]>=last:\n",
    "                continue\n",
    "            \n",
    "            #print(order)\n",
    "            \n",
    "            #print(order,ls[i][0],last)\n",
    "            lastsum+=ls[i][0]-last\n",
    "            bisect.insort(order,ls[i][0])\n",
    "            last=order[k-1]\n",
    "            #print(last)\n",
    "           # print(lastsum)\n",
    "            ans=min(ans,lastsum*ls[i][1]/ls[i][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        arr = sorted(zip(quality, wage), key=lambda x: -x[0] / x[1])\n",
    "        res = inf\n",
    "        heap = []\n",
    "        for quality, wage in arr:\n",
    "            tempres = wage\n",
    "            if len(heap) < k-1:\n",
    "                heappush(heap, (-quality, wage))\n",
    "                continue\n",
    "            for quality1, wage1 in heap:\n",
    "                tempres += wage * -quality1 / quality\n",
    "            res = min(res, tempres)\n",
    "            heappush(heap, (-quality, wage))\n",
    "            heappop(heap)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        arr = [(b/s, s) for b, s in zip(wage, quality)]\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        q1 = []\n",
    "        #q2 = []\n",
    "        tot = 0  \n",
    "        for i in range(k):\n",
    "            tot += arr[i][1]\n",
    "            heapq.heappush(q1, -arr[i][1]) \n",
    "        ans = tot * arr[k-1][0] \n",
    "        for i in range(k, n): \n",
    "            si = arr[i][1]\n",
    "            sk = -heapq.heappop(q1) \n",
    "            #heapq.heappush(q2, sk)\n",
    "            heapq.heappush(q1, -si)\n",
    "            tot += si - sk \n",
    "            ans = min(ans, tot * arr[i][0])\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        if k == 1:return min(wage)\n",
    "        q = []\n",
    "        stack = sorted([(w/v,v) for v , w in zip(quality,wage)])\n",
    "        l = 0\n",
    "        t_q = 0\n",
    "        ans = inf\n",
    "        for r , (rate , v) in enumerate(stack):\n",
    "            t_q += v\n",
    "            while len(q) + 1 == k:\n",
    "                ans = min(ans,t_q * rate)\n",
    "                t_q += heapq.heappop(q)\n",
    "            heapq.heappush(q,-v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        ratios = [(w/q, q) for q, w in zip(quality, wage)]\n",
    "        ratios.sort(key=lambda x: x[0])\n",
    "        maxHeap = []\n",
    "        ans = math.inf \n",
    "        qualitySum = 0\n",
    "        for ratio, q in ratios:\n",
    "            qualitySum += q \n",
    "            heappush(maxHeap, -q)\n",
    "            if len(maxHeap) > k:\n",
    "                qualitySum += heappop(maxHeap)\n",
    "            if len(maxHeap) == k:\n",
    "                ans = min(ans, qualitySum * ratio)\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "\n",
    "        a=sorted([(w/q,q) for q,w in zip(quality,wage)])\n",
    "        res=inf\n",
    "        heap=[]\n",
    "        s=0\n",
    "        for i,(r,q) in enumerate(a):\n",
    "            s+=q\n",
    "            heappush(heap,-q)\n",
    "            if i>=k-1:\n",
    "                res=min(res,s*r)\n",
    "                s+=heappop(heap)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        n = len(quality)\n",
    "        rec = [(wage[i]/quality[i], quality[i],wage[i]) for i in range(n)]\n",
    "        rec.sort(key=lambda x:x[0])\n",
    "        mheap = [-q for r,q,w in rec[:k]]\n",
    "        heapq.heapify(mheap)\n",
    "        sum_heap = -sum(mheap)\n",
    "        res = sum_heap * rec[k-1][0]\n",
    "        for i in range(k,n):\n",
    "            ri = rec[i][0]\n",
    "            if rec[i][1]<-mheap[0]:\n",
    "                sum_heap = sum_heap + heapq.heappop(mheap)\n",
    "                sum_heap += rec[i][1]\n",
    "                heapq.heappush(mheap, -rec[i][1])\n",
    "            res = min(res, ri*sum_heap)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        effs = [(q / w, q) for q, w in zip(quality, wage)]\n",
    "        effs.sort(key=lambda a: -a[0])\n",
    "        ans = float('inf')\n",
    "        h = []\n",
    "        total = 0\n",
    "        for rate, q in effs:\n",
    "            heapq.heappush(h, -q)\n",
    "            total += q\n",
    "            if len(h) > k:\n",
    "                total += heapq.heappop(h)\n",
    "            if len(h) == k:\n",
    "                ans = min(ans, total / rate)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        n = len(quality)\n",
    "        # heap = []\n",
    "        # for i in range(n):\n",
    "        #     heapq.heappush(heap, (wage[i] / quality[i], quality[i]))\n",
    "        # totalq = 0\n",
    "        # ppreq = 0\n",
    "        # for i in range(k):\n",
    "        #     item = heapq.heappop(heap)\n",
    "        #     ppreq = item[0]\n",
    "        #     totalq += item[1]\n",
    "        # return (totalq * ppreq)\n",
    "        price = [(wage[i] / quality[i], quality[i]) for i in range(n)]\n",
    "        price.sort()\n",
    "        maxkq = [0] * n\n",
    "        heap = []\n",
    "        t = 0\n",
    "        for i in range(k):\n",
    "            q = price[i][1]\n",
    "            heapq.heappush(heap, -q)\n",
    "            t = t + q\n",
    "        maxkq[k-1] = t\n",
    "        for i in range(k, n):\n",
    "            q = price[i][1]\n",
    "            if q + heap[0] < 0:\n",
    "                t = t + q + heapq.heappop(heap)\n",
    "                heapq.heappush(heap, -q)\n",
    "            maxkq[i] = t\n",
    "        ans = 1000000000\n",
    "        for i in range(k-1, n):\n",
    "            ans = min(ans, maxkq[i] * price[i][0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        worker = sorted([(w / q, q) for q, w in zip(quality, wage)])\n",
    "        qsum = 0\n",
    "        heap = []\n",
    "        res = float('inf')\n",
    "        for r, q in worker:\n",
    "            heapq.heappush(heap, - q)\n",
    "            qsum += q \n",
    "            if len(heap) > k:\n",
    "                qsum += heapq.heappop(heap)\n",
    "            if len(heap) == k:\n",
    "                res = min(res, r * qsum)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        import heapq\n",
    "        n = len(quality)\n",
    "        portion = []\n",
    "        for q, w in zip(quality, wage):\n",
    "            portion.append((w / q, q))\n",
    "        \n",
    "        portion.sort()\n",
    "        h = []\n",
    "        res = float('inf')\n",
    "        sum_q = 0\n",
    "        for p, q in portion:\n",
    "            heapq.heappush(h, - q)\n",
    "            sum_q += q\n",
    "            if len(h) > k:\n",
    "                sum_q -= - heapq.heappop(h)\n",
    "            \n",
    "            if len(h) == k:\n",
    "                res = min(res, - sum(h) * p)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        n = len(quality)\n",
    "        rate = [(w / q, q) for w, q in zip(wage, quality)]\n",
    "        rate.sort()\n",
    "        h = []\n",
    "        total = 0\n",
    "        ans = float('inf')\n",
    "        for r, q in rate:\n",
    "            heapq.heappush(h, -q)\n",
    "            total += q\n",
    "            if len(h) > k:\n",
    "                total += heapq.heappop(h)\n",
    "            if len(h) == k:\n",
    "                ans = min(ans, total * r)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        value = [w/q for w,q in zip(wage,quality)]\n",
    "        result = list(zip(value,quality,wage))\n",
    "        result.sort(key=lambda x : x[0])\n",
    "        qlist = [-x[1] for x in result[:k]]\n",
    "        heapq.heapify(qlist)\n",
    "        qsum = -sum(qlist)\n",
    "        res = qsum * result[k-1][0]\n",
    "        for worker in result[k:]:\n",
    "            if -worker[1] > qlist[0]:\n",
    "                maxworker = heapq.heapreplace(qlist,-worker[1])\n",
    "                qsum = qsum + maxworker + worker[1]\n",
    "                if qsum * worker[0] <= res:\n",
    "                    res = qsum * worker[0]\n",
    "        return(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        # ri = wage[i]/quality[i] 表示单位质量的工资，如果以 ri 为基准发工资，\n",
    "        # 那么r值低于ri的工人，都不低于最低工资\n",
    "        # 所以按照r值，升序排序，前面k-1个人都按照第k个人的r值发工资，总工资=sum(qulity)*ri\n",
    "        # 同时最大堆记录最小的k个quality，如果发现有更小的quality，更新堆，即有可能此时的总工资会更低\n",
    "        n = len(quality)\n",
    "        rec = [(wage[i]/quality[i], quality[i],wage[i]) for i in range(n)]\n",
    "        rec.sort(key=lambda x:x[0])\n",
    "        mheap = [-q for r,q,w in rec[:k]]\n",
    "        heapq.heapify(mheap)\n",
    "        sum_heap = -sum(mheap)\n",
    "        res = sum_heap * rec[k-1][0]\n",
    "        for i in range(k,n):\n",
    "            ri = rec[i][0]\n",
    "            if rec[i][1]<-mheap[0]:\n",
    "                sum_heap = sum_heap + heapq.heappop(mheap)\n",
    "                sum_heap += rec[i][1]\n",
    "                heapq.heappush(mheap, -rec[i][1])\n",
    "            res = min(res, ri*sum_heap)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        arr=[]\n",
    "        for q,w in zip(quality,wage):\n",
    "            p=w/q\n",
    "            arr.append([p,q])\n",
    "        n=len(arr)\n",
    "        arr.sort()\n",
    "        ans=100000000\n",
    "        totalwork=0\n",
    "        heap=[]\n",
    "        for i in range(k): \n",
    "            q=arr[i][1]\n",
    "            hq.heappush(heap,-q)\n",
    "            totalwork=totalwork+q\n",
    "        ans=totalwork*arr[k-1][0]\n",
    "        for i in range(k,n):\n",
    "            q=arr[i][1]\n",
    "            p=arr[i][0]\n",
    "            if q >= -heap[0]:\n",
    "                continue\n",
    "            tmp=-hq.heappop(heap)\n",
    "            hq.heappush(heap,-q)\n",
    "            totalwork=totalwork-tmp+q \n",
    "            ans=min(ans,totalwork*p)\n",
    "\n",
    "\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        n = len(quality)\n",
    "        weight = [(wage[i] / quality[i], i) for i in range(n)]\n",
    "        weight.sort()\n",
    "\n",
    "        que = []\n",
    "        s = 0\n",
    "        ans = float('inf')\n",
    "        for i in range(n):\n",
    "            w, id = weight[i]\n",
    "            if i <= k - 1 : \n",
    "                heappush(que, -quality[id]) # 大根堆\n",
    "                s += quality[id]\n",
    "            else :\n",
    "                if -que[0] > quality[id]:\n",
    "                    s += heappop(que)\n",
    "                    heappush(que, -quality[id])\n",
    "                    s += quality[id]\n",
    "            if i >= k - 1:\n",
    "                # print(s, w, s * w)\n",
    "                ans = min(ans, s * w)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        arr = sorted(zip(quality, wage), key=lambda x: x[1] / x[0])\n",
    "        heap = []\n",
    "        ans = 0\n",
    "        total = 0\n",
    "        for q, w in arr:\n",
    "            if len(heap) < k:\n",
    "                heappush(heap, (-q, w))\n",
    "                total += q\n",
    "                ans = total * w / q\n",
    "            else:\n",
    "                last_q, last_w = heap[0]\n",
    "                last_q *= -1\n",
    "                new_total = total - last_q + q\n",
    "                new_ans = new_total * w / q\n",
    "                if q < last_q:\n",
    "                    heappop(heap)\n",
    "                    heappush(heap, (-q, w))\n",
    "                    total = new_total\n",
    "                    ans = min(ans, new_ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        n = len(wage)\n",
    "        vals = [[wage[i] / quality[i], quality[i]] for i in range(n)]\n",
    "        vals.sort()\n",
    "        stack, ans, total = [], 1000000000, 0\n",
    "        for r, q in vals:\n",
    "            heapq.heappush(stack, -q)\n",
    "            total += q\n",
    "            if len(stack) > k: total += heapq.heappop(stack)\n",
    "            if len(stack) == k: ans = min(ans, r * total)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        if k==1: return min(wage)\n",
    "        # a b\n",
    "        # c d\n",
    "        # e f\n",
    "        # c<ad/b a\n",
    "        # c>ad/b cb/d>a c\n",
    "        # e>cf/d e\n",
    "        # e>cf/d>a/b*f/d=af/b\n",
    "        import functools\n",
    "        def compare(A, B):\n",
    "            a,b,c,d=A[0],A[1],B[0],B[1]\n",
    "            if c>a*d/b:\n",
    "                return -1\n",
    "            else:\n",
    "                return 1\n",
    "        p=[]\n",
    "        for _ in range(len(quality)):\n",
    "            p.append((wage[_],quality[_]))\n",
    "        p.sort(key=functools.cmp_to_key(compare))\n",
    "        # print(p)\n",
    "        res=inf\n",
    "        t=SortedList()\n",
    "        sumt=0\n",
    "        for _ in range(len(quality)):\n",
    "            if _<k-1:\n",
    "                t.add(p[_][1])\n",
    "                sumt+=p[_][1]\n",
    "            else:\n",
    "                c,d=p[_][0],p[_][1]\n",
    "                res=min(res, c*sumt/d+c)\n",
    "                if t[-1]>p[_][1]:\n",
    "                    x=t.pop(-1)\n",
    "                    sumt-=x\n",
    "                    t.add(p[_][1])\n",
    "                    sumt+=p[_][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        n = len(wage)\n",
    "        vals = [[wage[i] / quality[i], quality[i]] for i in range(n)]\n",
    "        vals.sort()\n",
    "        stack, ans, total = [], 1000000000, 0\n",
    "        for r, q in vals:\n",
    "            heapq.heappush(stack, -q)\n",
    "            total += q\n",
    "            if len(stack) > k: total += heapq.heappop(stack)\n",
    "            if len(stack) == k: ans = min(ans, r * total)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        n = len(quality)\n",
    "        qw = sorted([(-q,w,w/q) for q,w in zip(quality,wage)],key=lambda x:x[2])\n",
    "        r = qw[k-1][2]\n",
    "        ans = 0\n",
    "        sumQ = 0\n",
    "        for i in range(k):\n",
    "            ans += -qw[i][0]*r\n",
    "            sumQ += -qw[i][0]\n",
    "        # print(qw)\n",
    "        # print(sumQ,ans,r)\n",
    "        h = qw[:k]\n",
    "        heapify(h)\n",
    "        for i in range(k,n):\n",
    "            if qw[i][0] > h[0][0]:\n",
    "                r = qw[i][2]\n",
    "                sumQ -= -h[0][0]\n",
    "                sumQ += -qw[i][0]\n",
    "                heappop(h)\n",
    "                heappush(h,qw[i])\n",
    "                ans = min(ans, sumQ*r)\n",
    "        return ans\n",
    "\n",
    "                \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        qw=[]\n",
    "        for i in range(len(quality)):\n",
    "            qw.append([quality[i],wage[i],wage[i]/quality[i]])\n",
    "\n",
    "\n",
    "        #按照工资质量比，对工人进行排序\n",
    "        '''for i in range(len(qw)-1):\n",
    "            for j in range(1,len(qw)-i):\n",
    "                if qw[j-1][2]>qw[j][2]:\n",
    "                    qw[j],qw[j-1]=qw[j-1],qw[j]'''\n",
    "        qw=sorted(qw,key=lambda p:p[2])\n",
    "\n",
    "        len_worker=0\n",
    "        worker=[0]*k\n",
    "        s_i=0\n",
    "        \n",
    "        def insert_worker(i):\n",
    "            worker[len_worker]=i\n",
    "            son=len_worker\n",
    "            while son>0:\n",
    "                if qw[worker[son]][0]>qw[worker[(son-1)//2]][0]:\n",
    "                    worker[son],worker[(son-1)//2]=worker[(son-1)//2],worker[son]\n",
    "                    son=(son-1)//2\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "        def pop_worker():\n",
    "            worker[0]=worker[len_worker-1]\n",
    "            fa=0\n",
    "            while fa*2+1<=len_worker-2:\n",
    "                if fa*2+2>len_worker-2 or qw[worker[2*fa+1]][0]>qw[worker[fa*2+2]][0]:\n",
    "                    if qw[worker[fa]][0]<qw[worker[fa*2+1]][0]:\n",
    "                        worker[fa],worker[fa*2+1]=worker[fa*2+1],worker[fa]\n",
    "                        fa=fa*2+1\n",
    "                    else:\n",
    "                        break\n",
    "                else:\n",
    "                    if qw[worker[fa]][0]<qw[worker[fa*2+2]][0]:\n",
    "                        worker[fa],worker[fa*2+2]=worker[fa*2+2],worker[fa]\n",
    "                        fa=fa*2+2\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "        \n",
    "\n",
    "        #构造第1个候选组合\n",
    "        for i in range(k):\n",
    "            s_i=s_i+qw[i][0]#_________②_________\n",
    "            insert_worker(i)\n",
    "            len_worker+=1\n",
    "\n",
    "        ans=s_i*qw[i][2]\n",
    "\n",
    "        for i in range(k,len(qw)):\n",
    "            if  qw[i][0]<qw[worker[0]][0]:\n",
    "                s_i=s_i+qw[i][0]-qw[worker[0]][0]\n",
    "                pop_worker()\n",
    "                len_worker-=1\n",
    "                insert_worker(i)\n",
    "                len_worker+=1\n",
    "                if ans>s_i*qw[i][2]:\n",
    "                    ans=s_i*qw[i][2]\n",
    "                    \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "import heapq\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\r\n",
    "        \"\"\"使用最小堆\r\n",
    "\r\n",
    "        测试用例：\r\n",
    "        ```\r\n",
    "        [10,20,5]\\n[70,50,30]\\n2\r\n",
    "        [3,1,10,10,1]\\n[4,8,2,2,7]\\n3\r\n",
    "        ```\r\n",
    "        \"\"\"\r\n",
    "        # 按照 wage/quality 的比例排序\r\n",
    "        workers = sorted((w / q, q, w) for q, w in zip(quality, wage))\r\n",
    "\r\n",
    "        # 从比例最小的开始，依次加入堆中\r\n",
    "        # 堆中的元素为 (q, w)，表示当前的工人的 quality 和 wage\r\n",
    "        # 堆中的元素按照 quality 从大到小排序\r\n",
    "        # 堆中的元素的数量为 k，表示当前的工人的数量\r\n",
    "        # 堆中的元素的 quality 的和为 sum_q，表示当前的工人的 quality 的和\r\n",
    "        heap = []\r\n",
    "        sum_q = 0  # 当前的工人的 quality 的和\r\n",
    "        ans = float('inf')  # 当前的最小的 wage 的和\r\n",
    "        for r, q, w in workers:\r\n",
    "            heapq.heappush(heap, (-q, q, w))\r\n",
    "            sum_q += q\r\n",
    "            if len(heap) > k:\r\n",
    "                q, w = heapq.heappop(heap)[1:]\r\n",
    "                sum_q -= q\r\n",
    "            if len(heap) == k:\r\n",
    "                ans = min(ans, sum_q * r)  # 当前的最小的 wage 的和\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "import heapq\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\r\n",
    "        \"\"\"使用最小堆\r\n",
    "\r\n",
    "        测试用例：\r\n",
    "        ```\r\n",
    "        [10,20,5]\\n[70,50,30]\\n2\r\n",
    "        [3,1,10,10,1]\\n[4,8,2,2,7]\\n3\r\n",
    "        ```\r\n",
    "        \"\"\"\r\n",
    "        # 按照 wage/quality 的比例排序\r\n",
    "        workers = sorted((w / q, q, w) for q, w in zip(quality, wage))\r\n",
    "\r\n",
    "        # 从比例最小的开始，依次加入堆中\r\n",
    "        # 堆中的元素为 (q, w)，表示当前的工人的 quality 和 wage\r\n",
    "        # 堆中的元素按照 quality 从大到小排序\r\n",
    "        # 堆中的元素的数量为 k，表示当前的工人的数量\r\n",
    "        # 堆中的元素的 quality 的和为 sum_q，表示当前的工人的 quality 的和\r\n",
    "        # 堆中的元素的 wage 的和为 sum_w，表示当前的工人的 wage 的和\r\n",
    "        heap = []\r\n",
    "        sum_q = 0  # 当前的工人的 quality 的和\r\n",
    "        ans = float('inf')  # 当前的最小的 wage 的和\r\n",
    "        for r, q, w in workers:\r\n",
    "            heapq.heappush(heap, (-q, q, w))\r\n",
    "            sum_q += q\r\n",
    "            if len(heap) > k:\r\n",
    "                q, w = heapq.heappop(heap)[1:]\r\n",
    "                sum_q -= q\r\n",
    "            if len(heap) == k:\r\n",
    "                ans = min(ans, sum_q * r)  # 当前的最小的 wage 的和\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        A = [(w/q, q) for q, w in zip(quality, wage)]\n",
    "        A.sort(key = lambda x: (x[0], x[1]))\n",
    "        qsum, qpool = 0, []\n",
    "        for i in range(k):\n",
    "            qsum += A[i][1]\n",
    "            heapq.heappush(qpool, -A[i][1])\n",
    "        res = qsum * A[k-1][0]\n",
    "        for i in range(k, len(A)):\n",
    "            \"\"\"\n",
    "            这么写不对\n",
    "            cur = (qsum + qpool[0] + A[i][1]) * A[i][0]\n",
    "            if res > cur:\n",
    "                qsum += heapq.heappop(qpool) + A[i][1]\n",
    "                heapq.heappush(qpool, -A[i][1])\n",
    "                res = cur\n",
    "            \"\"\"\n",
    "            if A[i][1] < -qpool[0]:\n",
    "                qsum += heapq.heappop(qpool) + A[i][1]\n",
    "                heapq.heappush(qpool, -A[i][1])\n",
    "                if res > qsum * A[i][0]:\n",
    "                    res = qsum * A[i][0]\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        \"\"\"\n",
    "\n",
    "        :param quality:\n",
    "        :param wage:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if k == 1:\n",
    "            return min(wage)\n",
    "\n",
    "        sd1 = SortedList(key=lambda x: (x[0]))\n",
    "        q1 = 0\n",
    "        sd2 = SortedList()\n",
    "        for i in zip(quality, wage):\n",
    "            sd1.add((i[1] / i[0], i[0], i[1]))\n",
    "\n",
    "        curV = math.inf\n",
    "        wsd1 = SortedList()\n",
    "        qsd1 = SortedList()\n",
    "        cnt = 0\n",
    "        ratio = 0\n",
    "        qcnt = 0\n",
    "        for i in sd1:\n",
    "            if qcnt < k:\n",
    "                ratio = max(ratio, i[0])\n",
    "                qsd1.add(i[1])\n",
    "                cnt += i[1]\n",
    "                qcnt += 1\n",
    "                if qcnt == k:\n",
    "                    curV = min(curV, cnt * ratio)\n",
    "            else:\n",
    "\n",
    "                qsd1.add(i[1])\n",
    "                rem = qsd1.pop()\n",
    "\n",
    "                cnt -= rem\n",
    "                cnt += i[1]\n",
    "                ratio = i[0]\n",
    "\n",
    "                curV = min(curV, ratio * cnt)\n",
    "\n",
    "        return curV\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.mincostToHireWorkers(quality=[3, 1, 10, 10, 1], wage=[4, 8, 2, 2, 7], k=5))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:\n",
    "        \"\"\"\n",
    "\n",
    "        :param quality:\n",
    "        :param wage:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if k == 1:\n",
    "            return min(wage)\n",
    "        sd1 = SortedList(key=lambda x: (x[0]))\n",
    "        q1 = 0\n",
    "        sd2 = SortedList()\n",
    "        for i in zip(quality, wage):\n",
    "            sd1.add((i[1] / i[0], i[0], i[1]))\n",
    "\n",
    "        curV = math.inf\n",
    "        wsd1 = SortedList()\n",
    "        qsd1 = SortedList()\n",
    "        cnt = 0\n",
    "        ratio = 0\n",
    "        qcnt = 0\n",
    "        for i in sd1:\n",
    "            if qcnt < k:\n",
    "                ratio = max(ratio, i[0])\n",
    "                qsd1.add(i[1])\n",
    "                cnt += i[1]\n",
    "                qcnt += 1\n",
    "                if qcnt == k:\n",
    "                    curV = min(curV, cnt * ratio)\n",
    "            else:\n",
    "                qsd1.add(i[1])\n",
    "                rem = qsd1.pop()\n",
    "                cnt -= rem\n",
    "                cnt += i[1]\n",
    "                ratio = i[0]\n",
    "                curV = min(curV, ratio * cnt)\n",
    "        return curV\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
